/**
 * Created With IntelliJ IDEA
 * Description:leetcode:41. 缺失的第一个正数
 * <a href="https://leetcode.cn/problems/first-missing-positive/">...</a>
 * User: DELL
 * Data: 2023-03-29
 * Time: 17:43
 */


//原地哈希
//题解在 牛客网:BM53 缺失的第一个正整数 中
public class Solution {
    public int firstMissingPositive(int[] nums) {
        //题目规定数组不为空
        int len = nums.length;
        //第一遍遍历：将负数和0置为len+1
        for (int i = 0; i < len; i++) {
            if (nums[i] <= 0) {
                nums[i] = len+1;
            }
        }
        //第二次遍历：原地哈希
        for (int i = 0; i < len; i++) {
            int temp = Math.abs(nums[i]);
            if (temp <= len) {
                nums[temp-1] = -1 * Math.abs(nums[temp-1]);
            }
        }
        //第三次遍历：找出第一个为正数的元素
        for (int i = 0; i < len; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return len + 1;
    }
}